package com.huangyi;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - 猜数字大小II
        Solution solution1 = new Solution();
        System.out.println("猜数字大小II:");
        System.out.println("n = 10: " + solution1.getMoneyAmount(10));
        System.out.println("n = 1: " + solution1.getMoneyAmount(1));
        System.out.println("n = 2: " + solution1.getMoneyAmount(2));

        // 测试用例 - 矩阵中的最长递增路径
        Solution2 solution2 = new Solution2();
        System.out.println("\n矩阵中的最长递增路径:");
        int[][] matrix1 = {{9,9,4},{6,6,8},{2,1,1}};
        System.out.println("示例1: " + solution2.longestIncreasingPath(matrix1)); // 4
        int[][] matrix2 = {{3,4,5},{3,2,6},{2,2,1}};
        System.out.println("示例2: " + solution2.longestIncreasingPath(matrix2)); // 4
    }

    // 猜数字大小II
    static class Solution {
        int[][] memo;
        int n;

        public int getMoneyAmount(int _n) {
            n = _n;
            memo = new int[n + 1][n + 1];
            for (int[] x : memo) {
                Arrays.fill(x, -1);
            }
            return dfs(1, n);
        }

        public int dfs(int start, int end) {
            // 区间长度<=1，不需要猜测
            if (start >= end) return 0;

            // 已计算过，直接返回
            if (memo[start][end] != -1) return memo[start][end];

            int ret = Integer.MAX_VALUE;
            // 尝试第一次猜每个数i
            for (int i = start; i <= end; i++) {
                // 如果猜i，答案在左边[start, i-1]的代价
                int left = dfs(start, i - 1);
                // 如果猜i，答案在右边[i+1, end]的代价
                int right = dfs(i + 1, end);
                // 猜i的代价 = i + 最坏情况（对手恶意选择左或右）
                int cost = i + Math.max(left, right);
                // 在所有第一次猜测中，选择最优的
                ret = Math.min(ret, cost);
            }

            memo[start][end] = ret;
            return ret;
        }
    }

    // 矩阵中的最长递增路径
    static class Solution2 {
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        int m, n;
        int[][] memo;

        public int longestIncreasingPath(int[][] matrix) {
            m = matrix.length;
            n = matrix[0].length;
            memo = new int[m][n];
            // 默认值0表示未计算（路径长度至少为1，不会是0）

            int ret = 1;
            // 尝试每个格子作为起点
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    ret = Math.max(ret, dfs(matrix, i, j));
                }
            }
            return ret;
        }

        public int dfs(int[][] matrix, int si, int sj) {
            // 已计算过，直接返回
            if (memo[si][sj] != 0) return memo[si][sj];

            int ret = 1;  // 当前格子本身长度为1
            // 尝试四个方向
            for (int i = 0; i < 4; i++) {
                int x = si + dx[i], y = sj + dy[i];
                // 边界检查 + 递增条件
                if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[si][sj]) {
                    // 取四个方向中最长的路径 + 1
                    ret = Math.max(ret, dfs(matrix, x, y) + 1);
                }
            }

            memo[si][sj] = ret;
            return ret;
        }
    }
}